#include <stdio.h>
#include <string.h>
#include <math.h>
#include <cstring>
#include <iostream>
#include "des.h"
using namespace std;

int IP[64] = {                                     
	58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
	62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
	57, 49, 41, 33, 25, 17,  9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
	61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7 };

int IP_reverse[64] = {                            
	40, 8, 48, 16, 56, 24, 64, 32, 39, 7, 47, 15, 55, 23, 63, 31,
	38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,
	36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, 11, 51, 19, 59, 27,
	34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41,  9, 49, 17, 57, 25 };

int PC1[56] = {                               
	57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18,
	10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
	63, 55, 47, 39, 31, 23, 15,  7, 62, 54, 46, 38, 30, 22,
	14,  6, 61, 53, 45, 37, 29, 21, 13,  5, 28, 20, 12,  4 };

int PC2[48] = {                          
	14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10,
	23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2,
	41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
	44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32 };

int S[8][4][16] = {                     
	// S1   
	14, 4,  13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
	0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
	4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
	15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13,

	// S2   
	15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
	3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
	0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
	13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9,

	// S3   
	10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
	13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
	13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
	1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12,

	// S4   
	7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
	13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
	10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
	3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14,

	// S5   
	2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
	14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
	4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
	11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3,

	// S6   
	12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
	10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
	9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
	4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13,

	// S7   
	4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
	13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
	1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
	6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12,

	// S8   
	13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
	1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
	7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
	2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
};

int E[48] = {                                    
	32,  1,  2,  3,  4,  5,  4,  5,  6,  7,  8,  9,
	8,  9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
	16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
	24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32,  1 };

int P[32] = {                                            
	16, 7, 20, 21, 29, 12, 28, 17, 1,  15, 23, 26, 5,  18, 31, 10,
	2,  8, 24, 14, 32, 27, 3,  9,  19, 13, 30, 6,  22, 11, 4,  25 };


string des_encode(const char password[], string init_plain_text) {
	string plain_text, cyphertext = "";
	int result[80], len, temp_len;

	len = init_plain_text.length();

	for (int now_pos = 0; now_pos < len; now_pos = now_pos + 8) {
		plain_text = init_plain_text.substr(now_pos, min(8, len - now_pos));

		//puts("--------------------------------------------------------");
		//printf("Bits %d to %d of plaintext are processed here:\n", now_pos, now_pos - 1 + min(8, len - now_pos));
		if ((temp_len = plain_text.length()) < 8) {
			for (int j = 1; j <= 8 - temp_len; j++) {
				plain_text += 8 - temp_len;
			}
		}

		encode(plain_text.c_str(), password, result);


	//	puts("\nThe ciphertext is: ");
		for (int i = 0; i < 64; i++) {
			//printf("%d", result[i]);
			cyphertext += result[i];
		}

	}

	int lenc = cyphertext.length();

	for (int i = 0; i < lenc; i++) {
		cyphertext[i] += '0';
	}

	return cyphertext;
}

string des_decode(const char password[], string cyphertext) {
	string plain_text = "", frag_text;
	int len = cyphertext.length(), temp_cypher[64];
	char result_text[10];

	for (int i = 0; i < len; i++) {
		cyphertext[i] -= '0';
	}
	
	for (int i = 0; i < len; i += 64) {
		frag_text = cyphertext.substr(i, 64);

		for (int j = 0; j < 64; j++) {
			temp_cypher[j] = (int)frag_text[j];
		}


		decode(temp_cypher, password, result_text);

		for (int j = 0; j < 8; j++) {
			//printf("%c", result_text[j]);
			plain_text += result_text[j];
			int temp = 7 - j, k;
			for (k = j + 1; k < 8; k++) {
				if (result_text[k] != temp) {
					break;
				}
			}
			if (k >= 8) {
				break;
			}
		}
	}

	//puts("");

	//cout << "这里计算出的plain_text是：" << plain_text << "\n\n";


	return plain_text;
}


/*
* @ IP_replacement
* init IP replacement
* use table IP
*/
void IP_replacement(const int src[], int des[]) {
	int i;
	for (i = 0; i < 64; i++) {
		des[i] = src[IP[i] - 1];
	}
};

/*
* @ PC_1_replacement
* PC_1 replacement 
* 64 bits to 56 bits
* use table PC_1
*/
void PC_1_replacement(const int src[], int des[])  
{
	int i;
	for (i = 0; i < 56; i++) {
		des[i] = src[PC1[i] - 1];
	}
};

/*
* @ PC_2_replacement
* PC_2 replacement
* 56 bits to 48 bits
* use table PC_2
*/
void PC_2_replacement(const int src[], int des[]) {
	int i;
	for (i = 0; i < 48; i++)
	{
		des[i] = src[PC2[i] - 1];
	}
};

/*
* @ char_to_bit()
* convert char to 64-bit
* 0..7  for first char
* 8..15 for second char
* ...
* 
* pass test
*/
void char_to_bit(const char src[], int des[]) {

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			des[8 * i + (7 - j)] = (src[i] >> j) & 1;
		}
	}
}

/*
* @bit_to_char
* convert bit to char
* pass test
*/
void bit_to_char(const int src[], char des[]) {

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			des[i] = des[i] * 2 + src[i * 8 + j];
		}
	}
}

/*
* @cycle_left_shift
* left_shift for subkey
* pass test
*/
void cycle_left_shift(const int src[], int des[], int step) {
	int i;
	int len = 28;
	for (i = 0; i < len; i++){
		des[i] = src[(i + step) % len];
	}
};

/*
* @subkey_generate
* generate subkey from src to subkey
* pass test
*/
void subkey_generate(const int src[], int subkey[][48]) {
	int C[28], D[28], pc_1[56], temp_C[16][28], temp_D[16][28], step = 0, pc_2[16][56];

	PC_1_replacement(src, pc_1);

	for (int i = 0; i < 28; i++) {
		C[i] = pc_1[i];
		D[i] = pc_1[i + 28];
	}

	for (int i = 1; i <= 16; i++) {
		if (i == 1 || i == 2 || i == 9 || i == 16) {
			step += 1;
			cycle_left_shift(C, temp_C[i - 1], step);
			cycle_left_shift(D, temp_D[i - 1], step);
		}
		else {
			step += 2;
			cycle_left_shift(C, temp_C[i - 1], step);
			cycle_left_shift(D, temp_D[i - 1], step);
		}
	}

	for (int i = 0; i < 16; i++) {
		for (int j = 0; j < 28; j++) {
			pc_2[i][j] = temp_C[i][j];
			pc_2[i][j + 28] = temp_D[i][j];
		}
	}

	for (int i = 0; i < 16; i++)
	{
		PC_2_replacement(pc_2[i], subkey[i]);
	}
}

/*
* @E_extend
* pass test
*/
void E_extend(const int src[], int des[])
{
	int i;
	for (i = 0; i < 48; i++) {
		des[i] = src[E[i] - 1];
	}
};

/*
* @S_compress
* use S
* pass test
*/
void S_compress(const int src[], int des[]) {
	int i = 0;
	int j = 0;
	int temp[20];
	for (i = 0; i < 48; i = i + 6) {
		temp[j] = S[j][(src[i] << 1) + (src[i + 5])][(src[i + 1] << 3) + (src[i + 2] << 2) + (src[i + 3] << 1) + (src[i + 4])];
		j++;
	}
	for (j = 0; j < 8; j++) {
		for (i = 0; i < 4; i++) {
			des[3 * (j + 1) - i + j] = (temp[j] >> i) & 1;
		}
	}
};

/*
*@ Xor
* Xor array a and b
* pass test
*/
void Xor(int a[], int b[], int len) {
	int i;
	for (i = 0; i < len; i++) {
		a[i] = a[i] ^ b[i];
	}
};

/*
*@ P_replacement
* use table P
* pass test
*/
void P_replacement(const int src[], int des[]) {
	int i;
	for (i = 0; i < 32; i++) {
		des[i] = src[P[i] - 1];
	}
};

/*
*@ IP_inv
* use table IP_reverse
* pass test
*/
void IP_inv(const int src[], int des[]) {
	int i;
	for (i = 0; i < 64; i++) {
		des[i] = src[IP_reverse[i] - 1];
	}
};

/*
*@ wheel_transformation
* Feistel function
* pass test
*/
void wheel_transformation(int src[], int des[], int subkey[]) {
	int len = 48;
	int temp[48] = { 0 };
	int temp_1[32] = { 0 };

	E_extend(src, temp);
	Xor(temp, subkey, len);
	S_compress(temp, temp_1);
	P_replacement(temp_1, des);
}

void encode(const char plain_text[], const char password[], int des[]) {
	int after_ip[64], key[64], subkey[20][48], L[20][32], R[20][32], bits[70], temp_1[64];

	char_to_bit(plain_text, bits);
	char_to_bit(password, key);
	IP_replacement(bits, after_ip);
	subkey_generate(key, subkey);

	for (int i = 0; i < 32; i++) {
		L[0][i] = after_ip[i];
		R[0][i] = after_ip[32 + i];
	}

	for (int i = 1; i <= 15; i++) {
		for (int j = 0; j < 32; j++) {
			L[i][j] = R[i - 1][j];
		}
		wheel_transformation(R[i - 1], R[i], subkey[i - 1]);
		Xor(R[i], L[i - 1], 32);
	}

	for (int i = 0; i < 32; i++) {
		R[16][i] = R[15][i];
	}
	wheel_transformation(R[15], L[16], subkey[15]);
	Xor(L[16], L[15], 32);

	for (int i = 0; i < 32; i++) {
		temp_1[i] = R[16][i];
		temp_1[32 + i] = L[16][i];
	}

	IP_inv(temp_1, des);
}

void decode(int ciphertext[], const char password[], char des[]) {
	int after_ip[64], key[64], subkey[20][48], L[20][32], R[20][32], temp_1[64], temp_2[64];

	IP_replacement(ciphertext, after_ip);
	char_to_bit(password, key);
	subkey_generate(key, subkey);

	for (int i = 0; i < 32; i++) {
		R[0][i] = after_ip[i];
		L[0][i] = after_ip[32 + i];
	}

	for (int i = 1; i <= 15; i++) {
		for (int j = 0; j < 32; j++) {
			L[i][j] = R[i - 1][j];
		}
		wheel_transformation(R[i - 1], R[i], subkey[16 - i]);
		Xor(R[i], L[i - 1], 32);
	}

	for (int i = 0; i < 32; i++) {
		R[16][i] = R[15][i];
	}
	wheel_transformation(R[15], L[16], subkey[0]);
	Xor(L[16], L[15], 32);

	for (int i = 0; i < 32; i++) {
		temp_1[i] = L[16][i];
		temp_1[32 + i] = R[16][i];
	}

	IP_inv(temp_1, temp_2);
	bit_to_char(temp_2, des);
}
